LeetCode——不同路径II

NO.63 不同路径II 中等

思路一：动态规划 这道题和上一题作为姊妹题，没什么太大变化，只是多了障碍物这个因素。

dp[][]数组的含义：和上一题一样。

初始化：dp[0][0]~dp[0][n-1]即第一列和dp[0][0]~dp[0][n-1]即第一行因为只有向下或向右移动，所以在第一个障碍物之前的位置都是1，障碍物即障碍物之后的位置都是无法到达所以是0。

状态转移：如果[i][j]是障碍物则无法到达所以是0，否则依然是dp[i][j]=dp[i-1][j]+dp[i][j-1]，还是因为只能向下或向右移动，所以dp[i][j]的一定是从其上面的[i][j-1]或左面的[i-1][j]移动而来。

public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    int m = obstacleGrid.length,n=obstacleGrid[0].length;
    int[][] dp=new int[m][n];
    //初始化
    for (int i = 0; i < m; i++) {
        if (obstacleGrid[i][0]==0)dp[i][0]=1;
        else break;
    }
    for (int j = 0; j < n; j++) {
        if (obstacleGrid[0][j]==0)dp[0][j]=1;
        else break;
    }
    //状态转移
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            if (obstacleGrid[i][j]==1)dp[i][j]=0;
            else dp[i][j]=dp[i-1][j]+dp[i][j-1];
        }
    }
    return dp[m-1][n-1];
}

时间复杂度：O(m*n)

---

本人菜鸟，有错误请告知，感激不尽！

更多题解和学习记录博客:博客、github